class Heap {
  constructor(comparator = (a, b) => a - b, data = []) { // 首先是这个类的构造函数 接受两个参数,一个是构造器,默认是小顶堆,也就是递增的 可以对其进行改造,如果是对象可以斜撑a.val和b.val,第二个参数是数据 默认是一个空数组 ,也可以传入默认的数据
    this.data = data;
    this.comparator = comparator;//比较器
    this.heapify();//堆化函数
  }

  heapify () {
    if (this.size() < 2) return; // 如果个数小于2 没必要去堆化了 直接return
    for (let i = Math.floor(this.size() / 2) - 1; i >= 0; i--) { // 从第一个非叶子节点开始 一直到队首的节点
      this.bubbleDown(i);//bubbleDown操作  不断的向下移动 为什么叶子节点不用向下移动呢 因为叶子节点已经没有了下面的节点 不需要向下移动
    }
  }

  peek () { // 找到堆顶元素
    if (this.size() === 0) return null;
    return this.data[0];//查看堆顶
  }

  offer (value) { // 向堆中加入元素
    this.data.push(value); //加入数组
    this.bubbleUp(this.size() - 1); // 调整加入的元素在小顶堆中的位置 这个函数会将传入的节点不断的向上移动 传入的是末尾的size-1
  }

  poll () { // 取出堆顶的元素
    if (this.size() === 0) { // 如果堆的大小是0 就没有元素 返回null 就行了
      return null;
    }
    const result = this.data[0]; // 拿到堆顶的元素
    const last = this.data.pop(); // 拿到堆尾的元素
    if (this.size() !== 0) { // 如果节点的大小不是0 就进行节点的移动 使其符合定义
      this.data[0] = last;//交换第一个元素和最后一个元素 将堆尾的元素插入变成第一个元素
      this.bubbleDown(0);//bubbleDown操作 然后进行下移重新排序
    }
    return result; // 最后弹出堆顶的元素
  }

  bubbleUp (index) { // 传入当前的假如进来的节点的位置
    while (index > 0) { // 当位置大于0的时候不断的向上移动
      const parentIndex = (index - 1) >> 1; //父节点的位置
      //如果当前元素比父节点的元素小，就交换当前节点和父节点的位置
      if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { // 如果比较之后是小于0 就满足的构造器函数 需要进行交换 当前节点比父节点小就要交换
        // 如果是 b - a 的话 那就是大顶堆 就是当前节点比父节点大 那也要交换 所以只需要改构造器就行了
        this.swap(index, parentIndex);//交换自己和父节点的位置
        index = parentIndex;//不断向上取父节点进行比较
      } else {
        break;//如果当前元素比父节点的元素大，不需要处理
      }
    }
  }

  bubbleDown (index) {
    const lastIndex = this.size() - 1;//最后一个节点的位置
    while (true) {
      const leftIndex = index * 2 + 1;//左节点的位置
      const rightIndex = index * 2 + 2;//右节点的位置
      let findIndex = index;//bubbleDown节点的位置 默认值是当前的索引
      //找出左右节点中value小的节点
      if (
        leftIndex <= lastIndex &&
        this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 // 如果左节点的索引小于最后一个节点的索引,并且 传入比较器之后呢,左边的位置的数字小于当前的位置的数字 就让当前的节点位置变成左节点的位置
      ) {
        findIndex = leftIndex;
      }
      if (
        rightIndex <= lastIndex &&
        this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 // 右节点也是相同的道题
      ) {
        findIndex = rightIndex;
      }
      if (index !== findIndex) { // 执行完上面的判断之后 如果index不是findIndex了说明左右节点有小于当前节点的值
        this.swap(index, findIndex);//交换当前元素和左右节点中value小的
        index = findIndex; // 修改当前的index为记录的index 进行下一次循环
      } else {
        break; // 如果这个index还是和findIndex相等了,那就没必要继续判断了 因为下面没有比他小的了 直接退出循环即可
      }
    }
  }

  swap (index1, index2) {//交换堆中两个元素的位置
    [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
  }

  size () {
    return this.data.length;
  }
}